Some of the worst concurrency problems in multithreaded systems today are due to data races, which occur when there are unordered conflicting accesses in a program without proper synchronization. Data races are particularly problematic because data races manifest non-deterministically, often appearing only on very rare executions, making them notoriously difficult to test and debug.
Despite the numerous static and dynamic program analysis techniques in the literature, data races remain one of the most common bugs in modern concurrent software. Further, the techniques that do exist either have limited detection capability or are unsound, meaning that the techniques report false positives.
The present disclosure additionally addresses the detection and prediction of other violations such as atomicity violations, deadlocks, and null pointer dereferences, in addition to more generic properties typically not detected by current testing methods.
Predictive trace analysis (PTA) is an effective approach for detecting subtle bugs in concurrent programs. Existing PTA techniques, however, are typically based on ad-hoc algorithms tailored to low-level errors such as data races or atomicity violations, and are not applicable to high-level properties such as “a resource must be authenticated before use” and “a collection cannot be modified when being iterated over.” In addition, most techniques assume as input a globally ordered trace of events, which is expensive to collect in practice, as these techniques require synchronizing all threads.
Accordingly, there are a number of disadvantages with conventional methods of detecting and predicting violations or bugs in concurrent, multithreaded programs.